In this paper, the authors are interested in the problem of bilinear minimax games. By using tools from the optimization techniques of variance reduction, the authors show how to attain an eps-optimal (in additive error) solution to the problem in total time nnz(A) sqrt{nnz(A)*n}/eps. Furthermore, their results hold for both l_1 - l_1 and l_1 - l_2 games. One of the key technical contributions is an approach called "sampling from the difference", which leads to a desired variance bound. Various results in computational geometry, such as maximum inscribed ball and minimum enclosing ball, can also be recovered from these results.